import java.awt.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class MinesweeperPlayer {
	/**
	 * Attempts to identify the locations of all mine tiles on a
	 * Minesweeper board.  If the method can deduce the locations of all the
	 * hidden mines without revealing any mine tiles, it should return a
	 * collection of all the hidden mine locations.  If the method reveals a
	 * mine tile during the course of its operation, it should return a
	 * collection of all the hidden mine locations deduced up to that point.
	 *
	 * @param board A Minesweeper board.
	 * @return A collection of locations on the specified board that contain
	 * mine tiles. Note: {@link MinesweeperBoard} uses a row/column
	 * coordinate system while {@link Point} uses an x/y coordinate system.
	 */
	public static Collection<Point> solve(MinesweeperBoard board) {
		/**
		 * To store the suspected mines
		 */
		Set<Point> flags = new HashSet<Point>();
		/**
		 * Stores points I believe to be safe to reveal
		 */
		Queue<Point> knownSafePoints = new ConcurrentLinkedQueue<Point>();
		/**
		 * Stores points that have unrevealed neighbors
		 */
		Set<Point> pointsToExplore = new HashSet<Point>();
		
		// pick a random starting point
		Random random = new Random(System.currentTimeMillis());
		System.out.println("board size is " + board.getHeight() + "x" + board.getWidth());
		Point startPoint = new Point(random.nextInt(board.getWidth()),random.nextInt(board.getHeight()));

		// Pick the same starting point (for debugging) 
		//Point startPoint = new Point(4,0);
		
		// If the game hasn't been won, explore all the neighbors of revealed tiles that have neighbors
		if(!checkSolution(board, flags))
			expand(board,startPoint, knownSafePoints, pointsToExplore, flags);
		return flags;
		
	}
	
	/**
	 * Takes a starting point in, determines which neighbors are known to be safe and
	 * recursively reveals them. For example, if a tile is revealed and has a value
	 * of zero, (no neighboring mines) all of its neighbors are then expanded as well
	 * 
	 * @param board a MinesweeperBoard
	 * @param point a Point to be expanded (starting point)
	 * @param knownSafePoints A collection of points that can safely be expanded
	 * @param pointsToExplore A collection of tile points that have been revealed and have values > 0
	 * @param flags A collection of tile points that are believed to be mines
	 */
	private static void expand(MinesweeperBoard board, Point point, Queue<Point> knownSafePoints, Set<Point> pointsToExplore, Set<Point> flags)
	{
		
		boolean steppedOnMine = false;
		boolean foundSolution = false;
		int[] neighbors = {-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
		
		knownSafePoints.add(point); // put only known safe points in here!
		
		while(!knownSafePoints.isEmpty() && !steppedOnMine )
		{
			Point currentPoint = knownSafePoints.poll();
			if (board.getTile(currentPoint.y, currentPoint.x) == MinesweeperBoard.HIDDEN)
			{
				board.revealTile(currentPoint.y, currentPoint.x);
/*
				if(board.getTile(currentPoint.y, currentPoint.x) == MinesweeperBoard.MINE)
				{
					steppedOnMine = true;
					System.out.println("BOOM " + ("(" +currentPoint.getY() + "," + currentPoint.getX() +")"));
					System.exit(0);
				}
				else
				{
					System.out.println(board);
				}
*/
			}
			
			if (board.getTile(currentPoint.y, currentPoint.x) == 0)
			{
				// reveal all neighbors, add safe ones to toExplore
				for(int i=0;i<neighbors.length;i+=2)
				{
					int neighborY = currentPoint.y + neighbors[i];
					int neighborX = currentPoint.x + neighbors[i+1];
					if (neighborX >= 0 && neighborX < board.getWidth() &&
							neighborY >= 0 && neighborY < board.getHeight())
					{
						if (board.getTile(neighborY, neighborX) == MinesweeperBoard.HIDDEN)
						{
							board.revealTile(neighborY, neighborX);
							if(board.getTile(neighborY, neighborX) == 0)
							{ // its safe, add it to toExplore
								knownSafePoints.add(new Point(neighborX, neighborY));
							}
							else if(board.getTile(neighborY, neighborX) > 0)
							{// not known safe, process it later using some logic
								pointsToExplore.add(new Point(neighborX, neighborY));
							}
						}
					} // if neighborX > 0 ...etc
				}
			}
/*
			else if (board.getTile(currentPoint.y, currentPoint.x) < 9)
			{
				// TODO great, neighbors are mines, no clue as to safe moves -- Go to stage2
				System.out.println("no safe moves from " + currentPoint + " have to guess");
			}
*/
		} // end while known safe points
		if(!checkSolution(board, flags))
			checkEasySolutions(board, knownSafePoints, pointsToExplore, flags);
	}
	
	/** 
	 *  For each point P in pointsToExplore, apply the following logic:
	 *  if the number of P's children that are flags is equal to P's value then all 
	 *  unrevealed children of P are safe to expand.  If the number of P's children that
	 *  are unrevealed is equal to P's value - the number of P's children that are flags then
	 *  the unrevealed children must be mines. 
	 * @param board MinesweeperBoard the game state
	 * @param knownSafePoints tile points that are safe to reveal
	 * @param pointsToExplore tile points that 
	 * @param flags
	 */
	private static void checkEasySolutions(MinesweeperBoard board, Queue<Point> knownSafePoints, Set<Point> pointsToExplore, Set<Point> flags)
	{
		// note if any new tiles were revealed on this run, if not, don't need to repeat
		// if so, it's worth running again to see if a reveal tells us anything new
		boolean foundAMove=false;
		int[] neighbors = {-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
		
		// convert to an array because iterator over pointsToExplore caused 
		// a concurrentModification Exception
		Point[] toExplore = pointsToExplore.toArray(new Point[pointsToExplore.size()]);
		// look at each point to explore and decide by logic if all neighbors 
		// can be expanded or flagged
		for(int exploreIndex = 0;exploreIndex < toExplore.length;exploreIndex++)	
		{	

			Point currentPoint = toExplore[exploreIndex];
			// value holds the number of neighbors of currentPoint that are mines
			int value = board.getTile((int)currentPoint.getY(), (int)currentPoint.getX());
			int flagCount = 0; // the number of neighbors that have been flagged
			int hiddenCount = 0; // the number of neighbors that are not yet revealed
			// hold the list of neighbors of currentPoint
			Queue<Point> neighborPoints = new ConcurrentLinkedQueue<Point>();
			// count up neighboring flags and hidden tiles
			for(int i=0;i< neighbors.length;i+=2)
			{
				double neighborX = currentPoint.getX() + neighbors[i+1];
				double neighborY = currentPoint.getY() + neighbors[i];
				Point neighborPoint = null;
				// if the neighbor is within bounds of the board, process it
				if(neighborX >= 0 && neighborX < board.getWidth() && neighborY >= 0 && neighborY < board.getHeight())
				{					
					neighborPoint = new Point(currentPoint.x + neighbors[i+1], currentPoint.y + neighbors[i]);
					if(board.getTile((int)neighborPoint.getY(), (int)neighborPoint.getX()) == MinesweeperBoard.HIDDEN)
					{
						if(flags.contains(neighborPoint))
							flagCount++;
						else
						{
							hiddenCount++;
							neighborPoints.add(neighborPoint);
						}
					} // end if tile is hidden
				} // if neighbor is in range			
			}// end for neighbors all neighbors have been processed
			if(hiddenCount == (value - flagCount)) // because I don't consider flags hidden
			{
				while(!neighborPoints.isEmpty())
				{
					Point p = neighborPoints.poll();
					flags.add(p);
					foundAMove = true;
				}
			}
			// if flags = value then put all neighborPoints into knownSafePoints and call expand
			else if (flagCount == value)
			{
				while(!neighborPoints.isEmpty())
				{
					knownSafePoints.add(neighborPoints.poll());
					foundAMove = true;
				}
			}
			// if logical analysis has determined any tiles to be safe, reveal them and their neighbors
			if(!knownSafePoints.isEmpty())
				expand(board,knownSafePoints.poll(), knownSafePoints, pointsToExplore, flags);
			}// end while
		
			/*
			 * Have now expanded all tiles that logic can determine to be safe.
			 * is it possible that in the process, we've learned something that can 
			 * identify other safe tiles?  Should probably re-run over the entire board
			 * until no new possibilities are found before proceeding to guessing
			 */
			if(!checkSolution(board, flags))
				guessPoint(board, knownSafePoints, pointsToExplore, flags);	
	}// end checkEasySolutions
	
	/**
	 * Select a new starting point. Logical processing proivdes no sure next step
	 * so must rely on luck
	 * @param board
	 * @param knownSafePoints
	 * @param pointsToExplore
	 * @param flags
	 */
	public static void guessPoint(MinesweeperBoard board, Queue<Point> knownSafePoints, Set<Point> pointsToExplore, Set<Point> flags)
	{
		// pick a random starting point -- TODO be smarter about it
		Point restartPoint = null;
		while(restartPoint == null || (board.getTile((int)restartPoint.getY(), (int)restartPoint.getX()) != MinesweeperBoard.HIDDEN) || flags.contains(restartPoint))
		{
			Random random = new Random(System.currentTimeMillis());
			restartPoint = new Point(random.nextInt(board.getWidth()),random.nextInt(board.getHeight()));
		}
		expand(board,restartPoint, knownSafePoints, pointsToExplore, flags);	
	}
	
	/**
	 * Check to see if the game has been won
	 * @param board
	 * @param flags
	 * @return
	 */
	public static boolean checkSolution(MinesweeperBoard board, Set<Point> flags)
	{
		int unknownCount = 0;
		for(int i=0;i<board.getHeight();i++)
			for(int j=0;j<board.getWidth();j++)
				if(board.getTile(i, j) == MinesweeperBoard.HIDDEN)
					unknownCount++;
		if(unknownCount == flags.size())
			return true;
		else
			return false;
	}
}
